package bch.maven.plugin.guava.business;

import cn.hutool.core.lang.Pair;

import java.util.*;

public class GraphTraversalExample {

    public static void main(String[] args) {
        // 模拟血缘关系：key=子节点, value=(父亲, 母亲)
        Map<Long, Pair<Long, Long>> parentMap = new HashMap<>();
        parentMap.put(1L, Pair.of(2L, 3L));
        parentMap.put(2L, Pair.of(3L, null));
        parentMap.put(3L, Pair.of(1L, null));
        parentMap.put(4L, Pair.of(5L, 6L));
        parentMap.put(5L, Pair.of(6L, 4L));

        System.out.println("=== DFS Traversal ===");
        dfsTraversal(parentMap, 1L, new HashSet<>());

        System.out.println("\n=== BFS Traversal ===");
        bfsTraversal(parentMap, 1L);
    }

    // ================= DFS 深度优先搜索 =================
    private static void dfsTraversal(Map<Long, Pair<Long, Long>> parentMap, Long start, Set<Long> visited) {
        if (start == null || visited.contains(start)) return;

        System.out.println("Visiting: " + start);
        visited.add(start);

        Pair<Long, Long> parents = parentMap.get(start);
        if (parents != null) {
            dfsTraversal(parentMap, parents.getKey(), visited);   // 父亲
            dfsTraversal(parentMap, parents.getValue(), visited); // 母亲
        }
    }

    // ================= BFS 广度优先搜索 =================
    private static void bfsTraversal(Map<Long, Pair<Long, Long>> parentMap, Long start) {
        Set<Long> visited = new HashSet<>();
        Queue<Long> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Long node = queue.poll();
            if (node == null || visited.contains(node)) continue;

            System.out.println("Visiting: " + node);
            visited.add(node);

            Pair<Long, Long> parents = parentMap.get(node);
            if (parents != null) {
                if (parents.getKey() != null) queue.offer(parents.getKey());
                if (parents.getValue() != null) queue.offer(parents.getValue());
            }
        }
    }
}
